package algo_lignes_sites.data.pre_trt.pre_trt_path;

import algo_lignes_sites.data.junction.A_Junction.TypeJunction;
import algo_lignes_sites.data.junction.JunctionREF;
import algo_lignes_sites.data.junction.NodeData;
import algo_lignes_sites.data.path.A_Path;
import algo_lignes_sites.data.path.PathREF;
import algo_lignes_sites.params.Params_ls;
import algo_lignes_sites.params.objects.contraintesgeom.ContrainteGeomLine;
import commons.data.Attributes;
import commons.data.EchelleGeneralization;
import commons.io.in.File_in_Segment;
import commons.io.in.Point_in;
import commons.io.in.Segment_in;
import commons.logs.Logger;
import commons.spatialindex.simplegrid.SimpleGridSPI;
import commons.utils.UtilsGeom;
import commons.utils.primitive_geom.Point_d;
import gnu.trove.map.hash.THashMap;
import gnu.trove.set.hash.THashSet;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;


public class PathNodeCreator {

	private static THashSet<SegmentTopo> setSegTopo;

	// variable utile
	private static SegmentTopo[] tabSeg = new SegmentTopo[10];


	public static void createPathAndNodes(Params_ls params, ArrayList<PathREF> vPathREF, ArrayList<JunctionREF> vJunctionREF, ArrayList<JunctionREF> vNodeREF, SimpleGridSPI spi) {

		Logger.log_INFO1("-- Creation des Path et des Nodes --");

		// 0)
		// Avant de créer le moindre Path, il faut indiquer quelques informations statiques
		A_Path.setChampLibelleLine(params.champLibelleLine);
		A_Path.setChampTriLine(params.champTriLine, params.coucheLine.getTypeOf(params.champTriLine));
		A_Path.setbBiggestOnTop(params.bBiggestOnTopLine);
		// idem pour les Nodes
		NodeData.setChampLibelleNode(params.champLibelleNode);
		NodeData.setChampTriNode(params.champTriNode, params.coucheNode.getTypeOf(params.champTriNode));
		NodeData.setbBiggestOnTop(params.bBiggestOnTopNode);


		// 1)
		// On met a jour les Attributes du data_in afin qu'ils aient une version
		// restreinte selon les champs de fusion
		// (rappel on conserve malgré tout la totalité des attributs dans un autre vecteur
		//  pour d'éventuels msg d'erreur ultérieurs)
		((File_in_Segment)params.coucheLine).fusionneAttributes(params);

		// 2) Construction de la topologie élémentaire des données d'entrée
		
		// Fusion des nodes ayant le meme attribut (cf. paramétrage) et suffisamment proche
		// Depuis algo V22 (12/2014)
		fusioneNode(params, spi);
		
		//  on tente de snapper les éventuels futurs nodes isolés
		snapNodesIsoles(params, spi);
		//  on enregistre tous les nodes
		registerNodes(params, vNodeREF, spi);
		//  on enregistre toutes les extrémités de segment et on vérifie à combien de segments ils sont connectés
		registerExtrSegment(params, spi);

		vJunctionREF.addAll((ArrayList) spi.getAllObjects());

		// 3) Détermination du type des junctions
		determineTypeJunction(vJunctionREF);

		// 4) Création des path
		createAllPath(vPathREF);

		// 5) Si pas d'étape de snap de node sur les lignes, on vérifie si certain nodes sont isolé et on avertit l'utilisateur
		if (params.toleranceSnapNode<=0)
			warnIfNodeIsole(vJunctionREF);

		// 6) Vidage mémoire (pour aider le GC)
		clear(vJunctionREF);
	}

	// Détruit les objets éventuellement créés par ce module et supprime les liens statiques avec les objets passés en paramètres
	private static void clear(ArrayList<JunctionREF> vJunctionREF) {
		for (SegmentTopo seg : setSegTopo)
			seg.supprLien();
		setSegTopo.clear();
		setSegTopo=null;
		for (JunctionREF j : vJunctionREF) {
			if (j.setSegConnected != null)
				j.setSegConnected.clear();
			j.setSegConnected = null;
		}
	}
	
	
	//***********************************************************************************
	private static void fusioneNode(Params_ls params, SimpleGridSPI spiSeg) {
		Logger.log_INFO2(" - Fusion des nodes en doublon");
		
		if (!params.bFusionNodeDoublon) {
			Logger.log_INFO2("   -> OPTION DESACTIVEE");
			return;
		}

		
		Logger.log_INFO2("   sur l'attribut           : " + params.fusionNode_commonField);
		Logger.log_INFO2("   facteur dist/taille node : " + params.fusionNode_distMax);
		Logger.log_INFO2("   catégorie exclue         : " + params.fusionNode_catExcluded);
		
		ArrayList<Point_in> vNodes = (ArrayList<Point_in>)params.coucheNode.getObjects();
		ArrayList<Segment_in> vSeg = (ArrayList<Segment_in>)params.coucheLine.getObjects();
		
				
		spiSeg.clear();
		spiSeg.addObjects(vSeg);
		
		// 1ere passe pour avoir la liste des valeurs de champs de fusion avec doublons
		THashSet<String> setAllFieldFusionValues = new THashSet<>();
		THashMap<String, ArrayList<Point_in>> mapFieldFusionValuesWithDoublon_ListNode = new THashMap<>();
		
		for (Point_in node : vNodes) {
			if (node.attributes_in.isOfCategory(params.fusionNode_catExcluded))
				continue; // ce node ne doit pas subir ce traitement
			
			String val = node.attributes_in.getValue(params.fusionNode_commonField);
			if (setAllFieldFusionValues.contains(val)) {
				if (!mapFieldFusionValuesWithDoublon_ListNode.containsKey(val))
					mapFieldFusionValuesWithDoublon_ListNode.put(val, new ArrayList<Point_in>(6));
			} else
				setAllFieldFusionValues.add(val);
		}
		setAllFieldFusionValues = null; // liberation memoire
		
		// 2eme passe pour renseigner la map avec les listes de nodes en doublons
		for (Point_in node : vNodes) {
			if (node.attributes_in.isOfCategory(params.fusionNode_catExcluded))
				continue; // ce node ne doit pas subir ce traitement
			
			String val = node.attributes_in.getValue(params.fusionNode_commonField);
			if (mapFieldFusionValuesWithDoublon_ListNode.containsKey(val)) {
				mapFieldFusionValuesWithDoublon_ListNode.get(val).add(node);
			}
		}
		
		// A present, dans la map, on a comme clé, les valeurs du champs de fusion avec doublon ,
		//  associées a la liste des nodes concernés
		
		// Gestion d'un set de Point_in a supprimer en fin de traitement
		THashSet<Point_in> setNodeToDelete = new THashSet<Point_in>();
		THashSet<Segment_in> setSegToDeleteBecauseEmpty = new THashSet<>();
		
		// Pour chaque groupe de node en doublon, si le critere de distance entre node est respecté
		// on crée un nouveau node fusionné, avec des attributs sans interet
		// qui aura la plus grande des dimensions des nodes du groupe en doublon
		for (String valDoublon : mapFieldFusionValuesWithDoublon_ListNode.keySet()) {
			Logger.log_INFO2("   - traitement valeur : " + valDoublon);
			ArrayList<Point_in> listNodeDoublon = mapFieldFusionValuesWithDoublon_ListNode.get(valDoublon);
			
			// calcul du centre de gravité des nodes en doublon
			Point_d G = UtilsGeom.getCentreGravite(listNodeDoublon);
			
			// recup du node le plus gros
			Point_in biggestNode = null;
			for (Point_in node : listNodeDoublon) {
				if (biggestNode==null || node.contrainteGeomNode.diametre_papier_mm > biggestNode.contrainteGeomNode.diametre_papier_mm)
					biggestNode = node;
			}
			double rayonFinalBiggestNode = 0.5 * biggestNode.contrainteGeomNode.diametre_papier_mm/1000.0 * biggestNode.echelleGeneralization.echelle_inv;
			
			// vérif que les distances des nodes au centre de gravité sont en dessous du facteur * le rayon du plus gros node
			boolean bContinueWithThisListOfDoublon = true;
			for (Point_in node : listNodeDoublon) {
				
				double dist_Node_G = G.distTo(node);
				
				if (dist_Node_G > rayonFinalBiggestNode * params.fusionNode_distMax) {
					Logger.log_INFO2("    -> critere distance non satisfait");
					bContinueWithThisListOfDoublon = false;
					break;
				}
			}
			if (!bContinueWithThisListOfDoublon)
				// la liste courante ne respecte pas le critere de distance pour etre fusionnée
				continue;
			Logger.log_INFO2("    -> OK création d'un node temporaire au centre de gravité");
			
			// Creation d'un nouveau Point_in
			// on prend les attributs du plus gros node, mais on s'en fiche, en post-trt, il sera supprimé
			Point_in newNode = new Point_in(G.x, G.y, biggestNode.getAttributes_in());
			newNode.color = biggestNode.color;
			newNode.contrainteGeomNode = biggestNode.contrainteGeomNode;
			newNode.echelleGeneralization = biggestNode.echelleGeneralization;
			newNode.zones = biggestNode.zones;
			newNode.vNodeInitFusionne = listNodeDoublon; // on conserve les nodes initiaux : on les recréera en post traitement
			vNodes.add(newNode);
			
			
			// on change l'extrémité des segments qui étaient connectés aux anciens nodes pour les faire arriver au nouveau node			
			for (Point_in node : listNodeDoublon) {
				
				// on déplace tous les segments connectés à ce node
				ArrayList<Segment_in> vSegProche = (ArrayList) spiSeg.getObjectsThatMayIntersectWith(node);
				for (Segment_in seg : vSegProche) {
					if (setSegToDeleteBecauseEmpty.contains(seg)) continue; // va savoir ...
					if (seg.hasThisExtremity(node)) {
						if (seg.pt1.equalsXY(node)) {
							seg.pt1.x = newNode.x;
							seg.pt1.y = newNode.y;
						} else {
							assert(seg.pt2.equalsXY(node));
							seg.pt2.x = newNode.x;
							seg.pt2.y = newNode.y;
						}
						if (seg.getLength()<0.000001)
							// ce cas doit etre extremement rare mais au cas ou ...
							// on supprime le segment, car la suite des traitements suppose que les segments ne sont jamais vides
							//  (de tels segments dans les données d'entrée auront déjà été supprimé dans les pretraitement précédents)
							setSegToDeleteBecauseEmpty.add(seg);
					}
				}
				
//				Segment_in seg = new Segment_in(node, G, null);
//				seg.attributes_in = new Attributes(vSeg.get(0).getAttributes_in().getModel());
//				seg.attributes_fusion = new Attributes(vSeg.get(0).getAttributes_fusion().getModel());
//				seg.contrainteGeomLine = new ContrainteGeomLine(null, 0.001, 0.001, 0, null);
//				seg.echelleGeneralization = new EchelleGeneralization(null, null, 0);
//				vSeg.add(seg);
			}
			
			// flag des points_in comme étant a supprimer pour le traitement
			setNodeToDelete.addAll(listNodeDoublon);
			
		}
		
		// suppresion des nodes ayant ete fusionnés
		if (!setNodeToDelete.isEmpty()) {
			ArrayList<Point_in> vNodes_new = new ArrayList<Point_in>(vNodes.size() - setNodeToDelete.size());
			for (Point_in node : vNodes)
				if (!setNodeToDelete.contains(node))
					vNodes_new.add(node);
			
			params.coucheNode.setVObj(vNodes_new);
		}
		
		// suppresion des éventuel segments vide
		if (!setSegToDeleteBecauseEmpty.isEmpty()) {
			ArrayList<Segment_in> vSeg_new = new ArrayList<Segment_in>(vSeg.size() - setSegToDeleteBecauseEmpty.size());
			for (Segment_in seg : vSeg)
				if (!setSegToDeleteBecauseEmpty.contains(seg))
					vSeg_new.add(seg);
			
			params.coucheLine.setVObj(vSeg_new);
		}
		
	}
	
	
	//***********************************************************************************
	// Snappe les points représentant les futur node sur les extrémités des segments les plus proches
	//  dans le cas ou ils seraient isolés
	private static void snapNodesIsoles(Params_ls params, SimpleGridSPI spiPoints) {
		Logger.log_INFO2(" - Snap des nodes isolés sur les lignes (tolerance = " + params.toleranceSnapNode + " mètres)");
		if (params.toleranceSnapNode<=0) {
			Logger.log_INFO2("   -> rien à faire : tolérance de snap = " + params.toleranceSnapNode);
			return;
		}

		// D'abord on enregistre les coordonnées des futures junction (les extrémités des segments)
		ArrayList<Segment_in> vSegment = (ArrayList<Segment_in>)params.coucheLine.getObjects();
		spiPoints.clear();
		for (Segment_in seg : vSegment) {
			spiPoints.addPoint_siPasDejaPresent(seg.pt1);
			spiPoints.addPoint_siPasDejaPresent(seg.pt2);
		}

		// Puis on teste les nodes
		ArrayList<Point_in> vNodes = (ArrayList<Point_in>)params.coucheNode.getObjects();
		for (Point_in node_in : vNodes) {
			// Pas de souci le node est l'une des extrémité de segment
			if (spiPoints.isThisPointInSPI(node_in))
				continue;
			// Le node est isolé
			ArrayList<Point_d> vPointProches = spiPoints.getPointsAtDist(node_in, params.toleranceSnapNode, false);
			Point_d ptProche = UtilsGeom.getClosestPoint(node_in, vPointProches);
			if (ptProche != null && ptProche.distTo(node_in)<=params.toleranceSnapNode) {
				// On a trouvé une extrémité de segment dans la zone de tolérance
				// => on snappe le node
				node_in.x = ptProche.x;
				node_in.y = ptProche.y;
				Logger.log_INFO2("Node isolé : " + node_in.attributes_in.getValue(params.champLibelleNode) + " -> SNAP REUSSI");
			} else {
				Logger.log_WARN("Node isolé : " + node_in.attributes_in.getValue(params.champLibelleNode) + " -> aucune lignes dans la zone de tolérance");
			}
		}
	}
	
	// Crée lse Nodes et les enregistre dans le SPI et dans vNodeREF
	private static void registerNodes(Params_ls params,  ArrayList<JunctionREF> vNodeREF, SimpleGridSPI spiPoints) {
		spiPoints.clear();
		ArrayList<Point_in> vNodes = (ArrayList<Point_in>)params.coucheNode.getObjects();
		Logger.log_INFO2(" - Création des nodes (nb = " + vNodes.size() + ")");

		for (Point_in node_in : vNodes) {
			// Normalement il ne doit pas y avoir de doublon de node, le pre-traitement s'en est chargé au préalable
			assert(!spiPoints.isThisPointInSPI(node_in)) : "Node en doublon";

			JunctionREF nodeREF = new JunctionREF(node_in, node_in.attributes_in, node_in.zones, node_in.contrainteGeomNode, node_in.echelleGeneralization, node_in.color, node_in.vNodeInitFusionne);

			spiPoints.addPoint(nodeREF);
			vNodeREF.add(nodeREF);
		}
	}

	// Enregistre l'ensemble des autres points, c'est à dire les extrémités des segments
	private static void registerExtrSegment(Params_ls params, SimpleGridSPI spiPoints) {
		// spiPoint contient déjà les nodes : il ne faut pas l'effacer en début de traitement !
		setSegTopo = new THashSet<SegmentTopo>();

		ArrayList<Segment_in> vSegment = (ArrayList<Segment_in>)params.coucheLine.getObjects();
		Logger.log_INFO2(" - Création des junctions (nb = " + vSegment.size() + ")");


		for (Segment_in seg : vSegment) {

			JunctionREF j1, j2;
			j1 = (JunctionREF) spiPoints.getPointIfInSPI(seg.pt1);
			j2 = (JunctionREF) spiPoints.getPointIfInSPI(seg.pt2);

			if (j1 == null) {
				// 1ere fois qu'on rencontre ce point
				j1 = new JunctionREF(seg.pt1, TypeJunction.NOT_SET);
				spiPoints.addPoint(j1);
			}
			if (j2 == null) {
				// 1ere fois qu'on rencontre ce point
				j2 = new JunctionREF(seg.pt2, TypeJunction.NOT_SET);
				spiPoints.addPoint(j2);
			}

			// Creation du segmentTopo avec connexion des éléments entre eux
			SegmentTopo segTopo = new SegmentTopo(seg, j1, j2);
			j1.addSegment(segTopo);
			j2.addSegment(segTopo);
			setSegTopo.add(segTopo);
		}
	}


	// Avant meme de recoller les segments entre eux, on doit déterminer le type des junctions
	private static void determineTypeJunction(ArrayList<JunctionREF> vJunctionREF) {
		for (JunctionREF junc : vJunctionREF) {
			// On commence par les cas simples
			if (junc.isNode())
				continue; // a ce stade, les node ont déja le bon type de junction

			if (junc.nbSegConnected==0)
				// Impossible car ca doit etre un node isolé, et le test précédent interdit d'arriver la
				assert false;

			else if (junc.nbSegConnected==1) {
				// C'est forcément une junction standard
				junc.setTypeJunction(TypeJunction.STD);
			}
			else if (junc.nbSegConnected==2) {
				// Si les 2 segments peuvent faire partie du meme path -> STD
				// sinon, -> CONNECT_2
				tabSeg = junc.setSegConnected.toArray(tabSeg);
				if (couldBeSamePath (tabSeg[0], tabSeg[1]))
					junc.setTypeJunction(TypeJunction.STD);
				else
					junc.setTypeJunction(TypeJunction.CONNECT_2);
			}
			// Cas plus complexes
			else if (junc.nbSegConnected==4) {
				// Si 2 seg 2à2 peuvent faire partie du meme path -> INTERSECT
				// Sinon -> CONNECT_3
				tabSeg = junc.setSegConnected.toArray(tabSeg);
				SegmentTopo seg0 = tabSeg[0];
				SegmentTopo seg1 = tabSeg[1];
				SegmentTopo seg2 = tabSeg[2];
				SegmentTopo seg3 = tabSeg[3];

				if ( (couldBeSamePath(seg0, seg1) && couldBeSamePath(seg2, seg3) && !couldBeSamePath(seg0, seg2) && isThereRealCroisement(junc, seg0, seg1, seg2, seg3)) ||
					 (couldBeSamePath(seg0, seg2) && couldBeSamePath(seg1, seg3) && !couldBeSamePath(seg0, seg1) && isThereRealCroisement(junc, seg0, seg2, seg1, seg3)) ||
					 (couldBeSamePath(seg0, seg3) && couldBeSamePath(seg1, seg2) && !couldBeSamePath(seg0, seg1) && isThereRealCroisement(junc, seg0, seg3, seg1, seg2)) )

					junc.setTypeJunction(TypeJunction.INTERSECT);
				else
					junc.setTypeJunction(TypeJunction.CONNECT_3);

			}
			else if (junc.nbSegConnected%2==1) {
				// Nombre impair de segment -> forcément CONNECT_3
				// A ce stade du pre-traitement, on impose qu'un intersection doit etre stricte pour tous les path qui s'intersectent
				junc.setTypeJunction(TypeJunction.CONNECT_3);
			}
			// Encore plus complexe ... (plus lent à déterminer mais plus rare)
			else {
				// Nombre pair de segment (>=6) -> généralisation du cas à 4 segments
				// (on ne teste pas l'histoire des angles ici, trop complexe ...)
				// S'il y a toujours exactement 2 segments 2à2 qui peuvent faire partie du meme path -> INTERSECT
				// sinon, -> CONNECT_3
				tabSeg = junc.setSegConnected.toArray(tabSeg);
				for (int i=0 ; i<junc.nbSegConnected ; i++) {
					SegmentTopo seg = tabSeg[i];
					int nbSegMemePath = 0;
					for (int j=0 ; j<junc.nbSegConnected ; j++) {
						if (j==i) continue;
						SegmentTopo seg2 = tabSeg[j];
						if (couldBeSamePath(seg, seg2))
							nbSegMemePath++;
						if (nbSegMemePath>=2) break; // c'est fichu pour l'intersection, alors on arrete le test
					}
					if (nbSegMemePath!=1) {
						// Ca ne pourra jamais etre une intersection
						junc.setTypeJunction(TypeJunction.CONNECT_3);
						break;
					}
				}
				// En fin de for, si la junction est encore NOT_SET, c'est qu'elle est finalement une INTERSECT ...
				if (junc.isNotSet())
					junc.setTypeJunction(TypeJunction.INTERSECT);
			}
		}
	}


	// Determine si 2 segments pourraient faire partie du meme path, en ce qui concerne leurs attributs fusion, leur zone et leur contrainte geom
	// en realité, il feront peut etre partie de 2 path différent, par ex. s'ils sont séparés par un NODE ou un CONNECT_3
	// mais on ne connait pas encore le type de chaque junction à ce stade
	private static boolean couldBeSamePath(SegmentTopo seg1, SegmentTopo seg2) {
		return seg1.seg.attributes_fusion.equals(seg2.seg.attributes_fusion) &&
				seg1.seg.getZones().equals(seg2.seg.getZones()) &&
				seg1.seg.contrainteGeomLine.equals(seg2.seg.contrainteGeomLine) &&
				seg1.seg.echelleGeneralization.echelle_inv == seg2.seg.echelleGeneralization.echelle_inv &&
				seg1.seg.color.equals(seg2.seg.color);
	}

	// Détermine si les 4 segments pris 2 à 2 (0+1 et 2+3) se croisent réellement en JCenter et ne constituent
	//  pas une sorte de "double V tête-bêche"
	// Explication :
	// Cas special ou il y a 2 type Raccordement poste qui se rejoingne en J et que depuis J
	//  partent 2 ligne // de meme attrib fusion : alors J peut etre déterminée comme une intersection
	//  et les 2 lignes // ne seraient plus connectées au poste ! (apres simplif Node, elle pourraient meme etre
	//  déconnectées complètement si les Raccordements sont virés car dans le rayon de simplif
	//  => ce souci est corrigé en considérant que pour une
	//   junction multiple avec 4 segments, pour que ce soit une intersect, il faut les segment soit du meme path 2 à 2
	//   et QU'EN PLUS, ca se croise réellement (pas de double V tête bèche ...)
	// Cette subtilité n'est gérée que pour les junction à 4 segments, mais non gérée pour 6, 8 etc.
	private static boolean isThereRealCroisement(JunctionREF jCenter, SegmentTopo seg0, SegmentTopo seg1, SegmentTopo seg2, SegmentTopo seg3) {
		return UtilsGeom.isThereRealCroisement(jCenter, seg0.seg, seg1.seg, seg2.seg, seg3.seg);
	}


	//***********************************************************************************
	// Creation a proprement parler des Path
	private static void createAllPath(ArrayList<PathREF> vPathREF) {
		Logger.log_INFO2(" - Création des path");
		for (SegmentTopo seg : setSegTopo) {
			if (seg.bTraite) continue;
			vPathREF.add(createPathFromThisSeg(seg));
		}

		// Dans certains cas particulier, des junctions peuvent ne pas avoir le bon type en fin de traitement
		//  par exemple, un point triple -> connect3 mais qui correspond a un path qui fait une petite boucle a son bout
		//  on se retrouve avec un connect3 contenu par seulement 2 path ...
		for (PathREF path : vPathREF) {
			for (JunctionREF j : path.vJunctionREF)
				j.majTypeJunction();
		}
	}


	private static PathREF createPathFromThisSeg (SegmentTopo seg) {
		PathREF p = new PathREF(seg.seg.attributes_fusion, seg.seg.zones, seg.seg.contrainteGeomLine, seg.seg.echelleGeneralization, seg.seg.color);

		ArrayDeque<JunctionREF> pathJunctions = new ArrayDeque<JunctionREF>();

		// Ajout du 1er segment au path
		addSegToPathJunction(seg, pathJunctions);

		// Parcours des segments suivants, dans les 2 sens
		pacoursNextSeg_rec(seg, seg.j1, pathJunctions);
		pacoursNextSeg_rec(seg, seg.j2, pathJunctions);

		// Stockage des junctions dans le path
		for (JunctionREF j : pathJunctions) {
			p.addJunction(j);
			j.addPathContenant(p);
		}
		return p;
	}


	private static void pacoursNextSeg_rec(SegmentTopo seg, JunctionREF j, ArrayDeque<JunctionREF> pathJunctions) {
		// On ne poursuit que si la junction est un STD et avec 2 segments (!= extrémité libre) ou bien une INTERSECT
		if ((j.isStd() && j.nbSegConnected==2) || j.isIntersect()) {

			// On recherche un segment != seg et de mêmes attributs de fusion et de même zone
			for (SegmentTopo seg2 : j.setSegConnected) {
				if (seg2 == seg) continue; // normalement impossible car on retire les seg des junctions au fur et a mesure

				if (seg2.seg.attributes_fusion.equals(seg.seg.attributes_fusion) && seg2.seg.getZones().equals(seg.seg.getZones())) {
					// On a trouvé un segment à rajouter au path
					addSegToPathJunction (seg2, pathJunctions);

					// On poursuit recursivement le parcours avec ce nouveau seg
					if (seg2.j1 == j)
						pacoursNextSeg_rec(seg2, seg2.j2, pathJunctions);
					else {
						assert(seg2.j2==j);
						pacoursNextSeg_rec(seg2, seg2.j1, pathJunctions);
					}

					return;
				}
			}
			// On est obligé d'avoir trouvé un segment du fait que j a été déterminé comme étant un connectée à 2 segment
			//assert false; non car il existe un cas particulier : quand un path reboucle sur lui-même
		}
	}


	private static void addSegToPathJunction(SegmentTopo seg, ArrayDeque<JunctionREF> pathJunctions) {

		// On déclare le segment comme ajouté à un path
		seg.bTraite = true;

		if (pathJunctions.isEmpty()) {
			// 1er segment, on ajoute les 2 extrémités
			pathJunctions.add(seg.j1);
			pathJunctions.add(seg.j2);
		} else {
			// On doit n'ajouter qu'une des extrémités du segment
			JunctionREF jFirst = pathJunctions.getFirst();
			JunctionREF jLast = pathJunctions.getLast();

			// SIOUX : dans le cas d'un path qui fait une boucle, lors de l'ajout du dernier segment
			//  il y a 2 choix possibles de connexion.
			// Or il est possible qu'un node/connect3 soit l'une des 2 possibilités : il faut donc veiller
			//  à choisir l'extrémité qui n'est pas un node/connect3, d'où le test ci-dessous, ou l'on verifie
			//  qu'on ne connecte rien à un node/connect3
			if (jFirst == seg.j1 && !jFirst.isNode() && !jFirst.isConnect3())
				pathJunctions.addFirst(seg.j2);
			else if (jFirst == seg.j2 && !jFirst.isNode() && !jFirst.isConnect3())
				pathJunctions.addFirst(seg.j1);
			else if(jLast==seg.j1 && !jLast.isNode() && !jLast.isConnect3())
				pathJunctions.addLast(seg.j2);
			else if (jLast == seg.j2 && !jLast.isNode() && !jLast.isConnect3())
				pathJunctions.addLast(seg.j1);
			else
				assert false : "Impossible d'ajouter le segment : non connecté au path en cours !";
		}
		// On retire seg des junctionREF, cela accélère la recherche de segments pour les autres path
		seg.j1.removeSeg(seg);
		seg.j2.removeSeg(seg);
	}


	private static void warnIfNodeIsole(ArrayList<JunctionREF> vJunctionREF) {
		for (JunctionREF j : vJunctionREF)
			if (j.isNode() && j.nbSegConnected==0)
				Logger.log_INFO2("Node isolé : " + j);
	}


}
